#include <time.h>

/**
 * 函数名：CreateData
 * 功能：产生排序数据
 * 输入：接受数据的数组 *arr, 数据量 size
 * 输出：乱序的排序数据
*/
void CreateData(int *arr, int size){
    srand(0);
    for (int i = 0; i < size; ++i)
        arr[i] = rand() % (size*2);
}

/**
 * 函数名：swap
 * 功能：交换两个地址内的数据
 * 输入：两个待交换的变量地址
 * 输出：交换数据，返回void
*/
void swap(int* a, int* b){
    int t = *a;
    *a = *b;
    *b = t;
}

/**
 * 函数名：out_array
 * 功能：输出指定数量的数据
 * 输入：待输出的数组地址，输出的量
 * 输出：输出数组内的数据到控制台
*/
void out_array(int array[], int size){
    int size_ = sizeof(&array) / sizeof(int);
    printf("DataSize: %d\n", size_);
    if (size_ < size) size = size_;
    for (int i = 0; i < size; ++i) {
        printf("%d ", array[i]);
    }
    puts("... ... \n");
}


/**
 * 函数名：serial_BubbleSort
 * 功能：对数据进行串行的冒泡排序
 * 输入：待排数据地址，待排数据量
 * 输出：有序的数据，函数返回void
*/
void serial_BubbleSort(int *array, int size){
	int i, j;
	for (i = 0; i < size - 1; i++) 
	{
		for (j = 0; j < size - 1 - i; j++) 
		{
			if (array[j] > array[j + 1]) 
				// 交换两个元素的值
				swap(&array[j], &array[j + 1]);
		}
	}
}


/**
 * 函数名：serial_QuickSort
 * 功能：使用单线程快速排序算法对数据有序化
 * 输入：待排数据地址，待排数据的左边界，待排数据的右边界
 * 输出：有序的数据，函数返回void
*/
void serial_QuickSort(int arr[], int left, int right)
{
    int i, j, t, pivot;
 
    if (left > right)
        return;
 
    pivot = arr[left]; // 基准位
    i = left, j = right;

    while (i != j)
    {
        // 从右往左找小于基准位的数
        while (arr[j] >= pivot && i < j)
            j--;
        // 从左往右找大于基准位的数
        while (arr[i] <= pivot && i < j)
            i++;
        // 交换两个数在数组中的位置
        if (i < j)
            swap(&arr[i], &arr[j]);
    }

    arr[left] = arr[i];
    arr[i] = pivot;

    // 处理左、右，这里是一个递归的过程
    serial_QuickSort(arr, left, i - 1);
    serial_QuickSort(arr, i + 1, right);
}

/**
 * 函数名：serial_SelectSort
 * 功能：使用单线程选择排序算法对数据有序化
 * 输入：待排数据地址，待排数据量
 * 输出：有序的数据，函数返回void
*/
void serial_SelectSort(int *arr, int n)
{
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++)
    {
        min = i;
        for (j = i + 1; j < n; j++)
            if (arr[min] > arr[j])
                min = j;
        if (min != i)
            swap(&arr[i], &arr[min]);
    }
}


/**
 * function: put_time_info
 * 功能：输出时间分析
 * 输入：串行、并行开始时间
 * 输出：输出分析结果到控制台
*/
void put_time_info(char *filepath, char* sort_name, int size, int rank, double parallel_start, double parallel_end, double serial_start, double serial_end){
	double parallel_time = parallel_end - parallel_start;
	double serial_time = serial_end - serial_start;
    FILE *fp = fopen(filepath, "a");
	printf("The Name of sort: %s\n", sort_name);
	printf("Data size: -%d-\n", size);
	printf("The number of total processes: +%d+\n", rank);
	printf("Program parallel time: `%lf`s\n", parallel_time);
	printf("Program serial time: @%lf@s\n", serial_time);
	printf("Speedup: #%lf# \n", serial_time / parallel_time);
	fprintf(fp, "$$ ");
	fprintf(fp, "The Name of sort: %s | ", sort_name);
	fprintf(fp, "Data size: -%d- | ", size);
	fprintf(fp, "The number of total processes: +%d+ | ", rank);
	fprintf(fp, "Program parallel time: `%lf`s | ", parallel_time);
	fprintf(fp, "Program serial time: @%lf@s | ", serial_time);
	fprintf(fp, "Speedup: #%lf# | ", serial_time / parallel_time);
	fprintf(fp, "$$\n");
}


